package org.aplombh.java.leetcode.all;

public class _5最长回文子串 {
    public static void main(String[] args) {
        System.out.println(new Solution5_3().longestPalindrome("babad"));
    }
}

// 暴力解法
class Solution5_1 {
    public String longestPalindrome(String s) {
        char[] s1 = s.toCharArray();
        int max = 0, max_i = 0, max_j = 0, i = 0, j = 0, k = 0, p;

        for (i = 0; i < s1.length; i++) {
            for (j = s1.length - 1; j > i; j--) {
                for (k = j, p = 0; k > i; k--) {
                    if (s1[i + p] != s1[k]) {
                        p = 0;
                        break;
                    } else {
                        p++;
                    }
                }
                if (p > max) {
                    max = p;
                    max_i = i;
                    max_j = i + p;
                }
            }
        }
        return s.substring(max_i, max_j + 1);
    }
}

// 中心拓展
class Solution5_2 {
    public String longestPalindrome(String s) {
        char[] s1 = s.toCharArray();
        int max = 0, max_i = 0, max_j = 0, p, q;
        for (int i = 0, k = 0; i < s1.length; i++) {
            p = i;
            q = i;

            while (p >= 0 && q < s1.length && s1[p] == s1[q]) {
                p--;
                q++;
            }

            k = q - p - 2 + 1;
            if (k > max) {
                max = k;
                max_i = p + 1;
                max_j = q - 1;
            }

            if (i < s1.length - 1 && s1[i] == s1[i + 1]) {

                p = i;
                q = i + 1;

                while (p >= 0 && q < s1.length && s1[p] == s1[q]) {
                    p--;
                    q++;
                }

                k = q - p + 1 - 2;

                if (k > max) {
                    max = k;
                    max_i = p + 1;
                    max_j = q - 1;
                }
            }
        }
        return s.substring(max_i, max_j + 1);
    }
}

// 动态规划
class Solution5_3 {
    public String longestPalindrome(String s) {
        char[] s1 = s.toCharArray();
        int max = 1, max_i = 0, max_j = 0;
        // i <= j 上三角矩阵

        boolean[][] dp = new boolean[s.length() + 1][s.length() + 1];
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
            if (i < s.length() - 1 && s1[i] == s1[i + 1]) {
                dp[i][i + 1] = true;
                if (2 > max) {
                    max = 2;
                    max_i = i;
                    max_j = i + 1;
                }
            }
        }

        // 第几条斜对角线
        for (int p = 2; p < s1.length; p++) {
            // 斜对角线上第几个点
            for (int k = 0; k + p < s1.length; k++) {
                int j = k + p ;
                dp[k][j] = (s1[k] == s1[j]) && dp[k + 1][j - 1];
                if (dp[k][j] && j - k + 1 > max) {
                    max = j - k + 1;
                    max_i = k;
                    max_j = j;
                }
            }
        }
        return s.substring(max_i, max_j + 1);
    }
}